package com.dmzc.binarytree;

import java.util.Stack;

public class InOerder {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);
        root.left = n2;
        root.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        inOrder(root);
    }

    //递归的方法
    public static void inOrder(TreeNode root) {
        if (root == null) {
            System.out.println("#");
            return;
        }
        inOrder(root.left);
        System.out.println(root.value);
        inOrder(root.right);
    }


    //非递归的方法
    public static void inOrder1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode top;
        while (curr != null || !stack.empty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            top = stack.peek();
            stack.pop();
            System.out.println(curr.value);
            curr = top.right;
        }

    }


}

